home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_10 / 9n10043a < prev    next >
Encoding:
Text File  |  1991-07-08  |  1.9 KB  |  91 lines
  1. #include <stdio.h>
  2.  
  3. #define DEBUG
  4. #include "heaptst1.h"
  5.  
  6. #define MAX_LINE 256
  7.  
  8. struct node {
  9.     struct node * left;
  10.     struct node * right;
  11.     char * data;
  12. };
  13.  
  14. struct node * insert(struct node *, struct node *);
  15. struct node * build_node(char *);
  16. char * getnext(void);
  17. void walk_tree(struct node *);
  18. void free_tree(struct node *);
  19.  
  20. void main()
  21. {
  22.     char * word;
  23.     struct node *root, *new;
  24.  
  25.     root = NULL;
  26.         free(root);                /* error */
  27.  
  28.     do {
  29.         word = getnext();
  30.                 new = build_node(word);
  31.         root = insert(new,root);
  32.     } while (word != NULL);
  33.  
  34.         walk_tree(root);
  35.         free_tree(root);
  36.         exit(0);
  37. }
  38.  
  39. struct node * insert(struct node * new, struct node * tree)
  40. {
  41.         if (tree==NULL) return new;
  42.     if (new == NULL) return tree;
  43.     if (strcmp(new->data,tree->data) < 0)
  44.        tree->left = insert(new,tree->left);
  45.     else 
  46.        tree->right = insert(new,tree->right);
  47.     return tree;
  48. }
  49.      
  50. struct node * build_node(char * word)
  51. {
  52.     struct node * new;
  53.  
  54.     if (word == NULL) return NULL;
  55.     new = (struct node *) malloc( sizeof(struct node));
  56.         new->right = new->left = NULL;
  57.     new->data = word;
  58.     return new;
  59. }
  60.  
  61. char * getnext(void)
  62. {
  63.         char * new;
  64.     char buffer[MAX_LINE];
  65.     if ( gets(buffer) == NULL) return NULL;
  66.     new = (char *) malloc( strlen(buffer)+1);
  67.     strcpy(new,buffer);
  68.     return new;
  69. }
  70.  
  71. void walk_tree(struct node * tree)
  72. {
  73.         if (tree == NULL) return;
  74.     if (tree->left != NULL) walk_tree(tree->left);
  75.         if (tree->data != NULL) printf("%s\n",tree->data);
  76.         if (tree->right != NULL) walk_tree(tree->right);
  77. }
  78.  
  79. void free_tree(struct node * tree)
  80. { 
  81.     if (tree == NULL) return;
  82.     if (tree->left != NULL) 
  83.               free_tree(tree->left);
  84.     if (tree->right != NULL) 
  85.               free_tree(tree->right);
  86.     if (tree->data != NULL) 
  87.           free(tree->data);
  88.     free(tree);
  89.         free(tree);                 /* error */
  90. }
  91.